package com.example.arithmeticleetcode.leetcode.s2021.may;

import java.math.BigDecimal;
import java.time.LocalDate;
import java.time.LocalTime;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.TreeMap;
import java.util.stream.Collectors;

import org.springframework.util.CollectionUtils;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

public class Demo01 {
    public static void main(String[] args) {
        System.out.println(LocalTime.now());

    }

    public int maximumPopulation(int[][] logs) {
        return 0;
    }

    /**
     * 1848. 到目标元素的最小距离
     *
     * @param nums
     * @param target
     * @param start
     * @return
     */
    public int getMinDistance(int[] nums, int target, int start) {
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                min = Math.min(min, Math.abs(i - start));
            }
        }
        return min;
    }

    /**
     * 1828. 统计一个圆中点的数目
     *
     * @param points
     * @param queries
     * @return
     */
    public int[] countPoints(int[][] points, int[][] queries) {
        int[] resultArr = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int count = 0;
            for (int[] point : points) {
                double sqrt = Math.sqrt(Math.pow(Math.abs(point[0] - queries[i][0]), 2) + Math.pow(Math.abs(point[1] - queries[i][1]), 2));
                if (sqrt <= queries[i][2]) {
                    count++;
                }
            }
            resultArr[i] = count;
        }
        return resultArr;
    }


    /**
     * 1828. 统计一个圆中点的数目2
     *
     * @param points
     * @param queries
     * @return
     */
    public int[] countPoints2(int[][] points, int[][] queries) {
        int[] resultArr = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int count = 0;
            for (int[] point : points) {
                double sqrt = Math.pow(Math.abs(point[0] - queries[i][0]), 2) + Math.pow(Math.abs(point[1] - queries[i][1]), 2);
                if (sqrt <= Math.pow(queries[i][2], 2)) {
                    count++;
                }
            }
            resultArr[i] = count;
        }
        return resultArr;
    }

    /**
     * 1832. 判断句子是否为全字母句
     *
     * @param sentence
     * @return
     */
    public boolean checkIfPangram(String sentence) {
        if (sentence == null || sentence.length() < 26) {
            return false;
        }
        Set<Integer> set = new HashSet<>();
        char[] chars = sentence.toCharArray();
        for (char aChar : chars) {
            set.add((int) aChar);
        }
        return set.size() >= 26;
    }

    /**
     * 5742. 将句子排序
     *
     * @param s
     * @return
     */
    public String sortSentence(String s) {
        String[] strings = s.split(" ");
        String[] arrStr = new String[strings.length + 1];
        for (int i = 0; i < strings.length; i++) {
            char c = strings[i].charAt(strings[i].length() - 1);
            int index = Character.getType(c);
            arrStr[index] = strings[i].substring(0, strings[i].length() - 1);
        }
        StringBuilder sb = new StringBuilder();
        for (String s1 : arrStr) {
            sb.append(s1).append(" ");
        }
        return sb.substring(0, sb.length() - 1);
    }

    /**
     * 292. Nim 游戏
     *
     * @param n
     * @return
     */
    public boolean canWinNim(int n) {
        if (n < 4) return true;
        //todo
        return false;
    }


}

/**
 * 993. 二叉树的堂兄弟节点 深度优先算法
 */
class IsCousinsSolution {
    // x的信息
    int x;
    TreeNode xParent;
    int xDepth;
    boolean xFound = false;

    //y的信息
    int y;
    TreeNode yParent;
    int yDepth;
    boolean yFound = false;

    public boolean isCousins(TreeNode root, int x, int y) {
        this.x = x;
        this.y = y;
        dfs(root, 0, null);
        return xDepth == yDepth && xParent != yParent;
    }

    private void dfs(TreeNode node, int depth, TreeNode parent) {
        if (node == null) {
            return;
        }
        if (node.val == x) {
            xParent = parent;
            xDepth = depth;
            xFound = true;
        } else if (node.val == y) {
            yParent = parent;
            yDepth = depth;
            yFound = true;
        }

        if (xFound && yFound) {
            return;
        }

        dfs(node.left, depth + 1, node);

        if (xFound && yFound) {
            return;
        }

        dfs(node.right, depth + 1, node);

    }

    /**
     * 1442. 形成两个异或相等数组的三元组数目
     *
     * @param arr
     * @return
     */
    public int countTriplets1(int[] arr) {
        int n = arr.length;
        int[] s = new int[n + 1];
        for (int i = 0; i < n; i++) {
            s[i + 1] = s[i] ^ arr[i];
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j; k < n; k++) {
                    if (s[i] == s[k + 1]) ans++;
                }
            }
        }
        return ans;
    }

    /**
     * 1442. 形成两个异或相等数组的三元组数目
     *
     * @param arr
     * @return
     */
    public int countTriplets2(int[] arr) {
        int n = arr.length;
        int[] s = new int[n + 1];
        for (int i = 0; i < n; i++) {
            s[i + 1] = s[i] ^ arr[i];
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int k = i + 1; k < n; k++) {
                if (s[i] == s[k + 1]) ans += k - i;
            }
        }
        return ans;
    }

    /**
     * 1442. 形成两个异或相等数组的三元组数目
     *
     * @param arr
     * @return
     */
    public int countTriplets3(int[] arr) {
        int n = arr.length;
        int[] s = new int[n + 1];
        for (int i = 0; i < n; i++) {
            s[i + 1] = s[i] ^ arr[i];
        }
        int ans = 0;
        Map<Integer, Integer> cnt = new HashMap<>();
        Map<Integer, Integer> total = new HashMap<>();
        for (int k = 0; k < n; k++) {
            if (cnt.containsKey(s[k + 1])) {
                ans += cnt.get(s[k + 1]) * k - total.get(s[k + 1]);
            }
            cnt.put(s[k], cnt.getOrDefault(s[k], 0) + 1);
            total.put(s[k], total.getOrDefault(s[k], 0) + k);
        }
        return ans;
    }

    /**
     * 257. 二叉树的所有路径 广度优先算法
     *
     * @param root
     * @return
     */
    public List<String> binaryTreePathsBFS(TreeNode root) {
        List<String> paths = new ArrayList<>();
        if (root == null) return paths;
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        Queue<String> pathQuque = new LinkedList<>();
        nodeQueue.offer(root);
        pathQuque.offer(String.valueOf(root.val));
        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.poll();
            String path = pathQuque.poll();
            if (node.left == null && node.right == null) {
                paths.add(path);
            } else {
                if (node.left != null) {
                    nodeQueue.offer(node.left);
                    pathQuque.offer(path + "->" + node.left.val);
                }
                if (node.right != null) {
                    nodeQueue.offer(node.right);
                    pathQuque.offer(path + "->" + node.right.val);
                }
            }
        }
        return paths;
    }

    /**
     * 257. 二叉树的所有路径 深度优先算法
     *
     * @param root
     * @return
     */
    public List<String> binaryTreePathsDFS(TreeNode root) {
        List<String> paths = new ArrayList<>();
        dfs(root, "", paths);
        if (root == null) return paths;
        return paths;
    }

    private void dfs(TreeNode node, String path, List<String> paths) {
        if (node != null) {
            path += node.val;
            if (node.left == null && node.right == null) {
                paths.add(path);
            } else {
                dfs(node.left, path + "->", paths);
                dfs(node.right, path + "->", paths);
            }
        }
    }

    /**
     * 692. 前K个高频单词
     *
     * @param words
     * @param k
     * @return
     */
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        Map<Integer, List<String>> treeMap = new TreeMap<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            List<String> list = treeMap.getOrDefault(entry.getValue(), new ArrayList<String>());
            list.add(entry.getKey());
            treeMap.put(entry.getValue(), list);
        }

        List<String> result = new ArrayList<>();
        for (Map.Entry<Integer, List<String>> entry : treeMap.entrySet()) {
            List<String> list = entry.getValue();
            if (list.size() > 1) {
                Collections.sort(list);
            }
            for (String s : list) {
                result.add(s);
                k--;
                if (k < 1) {
                    return result;
                }
            }
        }
        return result;
    }

    /**
     * 692. 前K个高频单词
     *
     * @param words
     * @param k
     * @return
     */
    public List<String> topKFrequent2(String[] words, int k) {
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        List<String> result = new ArrayList<>();
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            result.add(entry.getKey());
        }
        Collections.sort(result, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return map.get(o1) == map.get(o2) ? o1.compareTo(o2) : map.get(o2) - map.get(o1);
            }
        });
        return result.subList(0, k);
    }

    /**
     * 692. 前K个高频单词 优先级队列
     *
     * @param words
     * @param k
     * @return
     */
    public List<String> topKFrequent3(String[] words, int k) {
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<Map.Entry<String, Integer>>((o1, o2) -> o1.getValue() == o2.getValue() ? o2.getKey().compareTo(o1.getKey()) : o1.getValue() - o2.getValue());

        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            pq.offer(entry);
            if (pq.size() > k) {
                pq.poll();
            }
        }

        List<String> list = new ArrayList<>();
        while (!pq.isEmpty()) {
            list.add(pq.poll().getKey());
        }
        Collections.reverse(list);
        return list;
    }

    /**
     * 1035. 不相交的线  动态规划去实现 是最长公共子序列的形态
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            int a = nums1[i - 1];
            for (int j = 0; j <= n; j++) {
                int b = nums2[j - 1];
                if (a == b) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m + 1][n + 1];
    }

    public static void main(String[] args) {
        checkZeroOnes("1101");
    }

    /**
     * 1869. 哪种连续子字符串更长
     *
     * @param s
     * @return
     */
    public static boolean checkZeroOnes(String s) {
        if (s == null || s.length() == 0) return false;
        char[] chars = s.toCharArray();
        int pre = chars[0];
        int oneMaxCount = pre == '1' ? 1 : 0, zeroMaxCount = oneMaxCount == 1 ? 0 : 1;
        int oneCount = oneMaxCount, zeroCount = zeroMaxCount;
        for (int i = 1; i < chars.length; i++) {
            if (pre == '1') {
                if (pre == chars[i]) {
                    oneCount++;
                } else {
                    oneCount = 0;
                    zeroCount = 1;
                }

            }
            if (pre == '0') {
                if (pre == chars[i]) {
                    zeroCount++;
                } else {
                    zeroCount = 0;
                    oneCount = 1;
                }
            }
            pre = chars[i];
            oneMaxCount = Math.max(oneCount, oneMaxCount);
            zeroMaxCount = Math.max(zeroCount, zeroMaxCount);
        }
        zeroMaxCount = Math.max(zeroCount, zeroMaxCount);
        oneMaxCount = Math.max(oneCount, oneMaxCount);
        return oneMaxCount > zeroMaxCount;
    }

    /**
     * 461. 汉明距离
     *
     * @param x
     * @param y
     * @return
     */
    public int hammingDistance1(int x, int y) {
        return Integer.bitCount(x ^ y);
    }

    /**
     * 461. 汉明距离
     *
     * @param x
     * @param y
     * @return
     */
    public int hammingDistance2(int x, int y) {
        int s = x ^ y, ret = 0;
        while (s != 0) {
            ret += s & 1;
            s >>= 1;
        }
        return ret;
    }

    /**
     * 461. 汉明距离
     *
     * @param x
     * @param y
     * @return
     */
    public int hammingDistance3(int x, int y) {
        int s = x ^ y, ret = 0;
        while (s != 0) {
            s &= s - 1;
            ret++;
        }
        return ret;
    }

    /**
     * 1190. 反转每对括号间的子串 使用栈实现
     *
     * @param s
     * @return
     */
    public String reverseParentheses(String s) {
        Deque<String> stack = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        char[] chars = s.toCharArray();
        for (char aChar : chars) {
            if (aChar == '(') {
                stack.push(sb.toString());
                sb.setLength(0);
            } else if (aChar == ')') {
                sb.reverse();
                sb.insert(0, stack.pop());
            } else {
                sb.append(aChar);
            }
        }
        return sb.toString();
    }

    /**
     * 1190. 反转每对括号间的子串 使用栈实现
     *
     * @param s
     * @return
     */
    public String reverseParentheses2(String s) {
        char[] chars = s.toCharArray();
        int[] arr = new int[chars.length];
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '(') {
                stack.push(i);
            } else if (chars[i] == ')') {
                int j = stack.pop();
                arr[i] = j;
                arr[j] = i;
            }
        }
        StringBuilder sb = new StringBuilder();
        int index = 0, step = 1;
        while (index < chars.length) {
            if (chars[index] == '(' || chars[index] == ')') {
                index = arr[index];
                step = -step;
            } else {
                sb.append(chars[index]);
            }
            index += step;
        }
        return sb.toString();
    }

    /**
     * 477. 汉明距离总和
     *
     * @param nums
     * @return
     */
    public int totalHammingDistance(int[] nums) {
        int sum = 0;
        for (int i = 0, iLen = nums.length - 1, jlen = nums.length; i < iLen; i++) {
            for (int j = i + 1; j < jlen; j++) {
                sum += totalHammingDistance(nums[i], nums[j]);
            }
        }
        return sum;
    }

    private int totalHammingDistance(int x, int y) {
        int sum = 0, or = x ^ y;
        while (or != 0) {
            sum += or & 1;
            or >>= 1;
        }
        return sum;
    }

    /**
     * 477. 汉明距离总和
     *
     * @param nums
     * @return
     */
    public int totalHammingDistance2(int[] nums) {
        int sum = 0;
        for (int i = 0, iLen = nums.length - 1, jlen = nums.length; i < iLen; i++) {
            for (int j = i + 1; j < jlen; j++) {
                sum += Integer.bitCount(nums[i] ^ nums[j]);
            }
        }
        return sum;
    }

    /**
     * 477. 汉明距离总和
     *
     * @param nums
     * @return
     */
    public int totalHammingDistance3(int[] nums) {
        int ans = 0, n = nums.length;
        for (int i = 0; i < 30; ++i) {
            int c = 0;
            for (int num : nums) {
                c += (num >> i) & 1;
            }
            ans += c * (n - c);
        }
        return ans;
    }
}


/**
 * 993. 二叉树的堂兄弟节点 广度优先算法
 */
class IsCousinsSolution2 {
    // x的信息
    int x;
    TreeNode xParent;
    int xDepth;
    boolean xFound = false;

    //y的信息
    int y;
    TreeNode yParent;
    int yDepth;
    boolean yFound = false;

    public boolean isCousins(TreeNode root, int x, int y) {
        this.x = x;
        this.y = y;

        Queue<TreeNode> nodeQueue = new LinkedList<>();
        Queue<Integer> depthQuque = new LinkedList<>();
        nodeQueue.offer(root);
        depthQuque.offer(0);
        update(root, null, 0);

        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.poll();
            int depth = depthQuque.poll();
            if (node.left != null) {
                nodeQueue.offer(node.left);
                depthQuque.offer(depth + 1);
                update(node.left, node, depth + 1);
            }
            if (node.right != null) {
                nodeQueue.offer(node.right);
                depthQuque.offer(depth + 1);
                update(node.right, node, depth + 1);
            }
            if (xFound && yFound) {
                break;
            }
        }
        return xParent != yParent && xDepth == yDepth;
    }

    private void update(TreeNode node, TreeNode parent, int depth) {
        if (node.val == x) {
            xParent = parent;
            xDepth = depth;
            xFound = true;
        } else if (node.val == y) {
            yParent = parent;
            yDepth = depth;
            yFound = true;
        }
    }

//    public static void main(String[] args) {
//        String str = "021";
//        System.out.println(Integer.parseInt(str));
//    }

    /**
     * 5772. 检查某单词是否等于两单词之和
     *
     * @param firstWord
     * @param secondWord
     * @param targetWord
     * @return
     */
    public boolean isSumEqual(String firstWord, String secondWord, String targetWord) {
        return getNum(firstWord) + getNum(secondWord) == getNum(targetWord);
    }

    private int getNum(String firstWord) {
        StringBuilder sb = new StringBuilder();
        for (char c : firstWord.toCharArray()) {
            sb.append(c - 97);
        }
        return Integer.parseInt(sb.toString());
    }

    /**
     * 342. 4的幂
     *
     * @param n
     * @return
     */
    public boolean isPowerOfFour(int n) {
        if (n == 1) return true;
        int yushu = 0;
        while (n > 0) {
            yushu = n & 1;
            if (yushu == 0 && n == 1) return true;
            n >>= 2;
        }
        return false;
    }

//    public static void main(String[] args) {
//        int[] nums = {1, 1, 1, 1, 1};
//        findTargetSumWays(nums, 3);
//    }

    /**
     * 494. 目标和
     *
     * @param nums
     * @param target
     * @return
     */
    private static int count;
    private static int countTotal;

    public static int findTargetSumWays(int[] nums, int target) {
        backTrack(nums, target, 0, 0);
        System.out.println(countTotal);
        return count;
    }

    private static void backTrack(int[] nums, int target, int index, int sum) {
        countTotal++;
        if (index == nums.length) {
            if (sum == target) {
                count++;
            }
        } else {
            System.out.println("第一  " + index + " " + sum);
            backTrack(nums, target, index + 1, sum + nums[index]);
            System.out.println("第二  " + index + " " + sum);
            backTrack(nums, target, index + 1, sum - nums[index]);
        }
    }

    /**
     * 494. 目标和
     *
     * @param nums
     * @param target
     * @return
     */
    public static int findTargetSumWaysDP(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int diff = sum - target;
        if (diff < 0 || (diff & 1) == 1) {
            return 0;
        }
        int n = nums.length, neg = diff >> 1;
        int[][] dp = new int[n + 1][neg + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            int num = nums[i - 1];
            for (int j = 0; j <= neg; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= num) {
                    dp[i][j] += dp[i - 1][j - num];
                }
            }
        }
        return dp[n][neg];
    }

//    public static void main(String[] args) {
//        List<DailyRealPublishInfo> orderDailyInfo = new ArrayList<>();
//        DailyRealPublishInfo dailyRealPublishInfo = new DailyRealPublishInfo();
//        dailyRealPublishInfo.setOrderId("1");
//        dailyRealPublishInfo.setDate(LocalDate.now());
//        dailyRealPublishInfo.setConsumeAmount(new BigDecimal("1.19"));
//        dailyRealPublishInfo.setCompensateCostAmount(new BigDecimal("1.19"));
//        orderDailyInfo.add(dailyRealPublishInfo);
//        Map<String, List<DailyRealPublishInfo>> map = new HashMap<>();
//
//
//        System.out.println("----------");
//        DailyRealPublishInfo dailyRealPublishInfo2 = new DailyRealPublishInfo();
//        dailyRealPublishInfo2.setOrderId("1");
//        dailyRealPublishInfo2.setDate(LocalDate.of(2021, 6, 6));
//        dailyRealPublishInfo2.setConsumeAmount(new BigDecimal("1"));
//        dailyRealPublishInfo2.setCompensateCostAmount(new BigDecimal("1"));
//        orderDailyInfo.add(dailyRealPublishInfo2);
//        map.put("1", orderDailyInfo);
//
//        Map<LocalDate, BigDecimal> localDateBigDecimalMap = getLocalDateBigDecimalMap(map, "1");
//        System.out.println(localDateBigDecimalMap);
//
//        Map<LocalDate, BigDecimal> map2 = orderDailyInfo.stream().collect(
//                toMap(DailyRealPublishInfo::getDate,
//                        info -> info.getConsumeAmount().add(info.getCompensateCostAmount())));
//        System.out.println(map2);
//    }


    private static Map<LocalDate, BigDecimal> getLocalDateBigDecimalMap(Map<String,
            List<DailyRealPublishInfo>> orderDailyInfo, String orderId) {
        if (!CollectionUtils.isEmpty(orderDailyInfo.get(orderId))) {
            return orderDailyInfo.get(orderId).stream().collect(
                    Collectors.toMap(DailyRealPublishInfo::getDate,
                            info -> info.getConsumeAmount().add(info.getCompensateCostAmount())));
        }
        return Collections.EMPTY_MAP;
    }

    /**
     * 1881. 插入后的最大值
     *
     * @param n
     * @param x
     * @return
     */
    public String maxValue(String n, int x) {
        char[] chars = n.toCharArray();
        StringBuilder sb = new StringBuilder();
        x += 48;
        boolean flag = true;
        if (chars[0] == '-') {
            sb.append(chars[0]);
            for (int i = 1; i < chars.length; i++) {
                if (flag && chars[i] < x) {
                    sb.append(x - 48);
                    flag = false;
                }
                sb.append(chars[i]);
            }
        } else {
            for (char aChar : chars) {
                if (flag && aChar < x) {
                    sb.append(x - 48);
                    flag = false;
                }
                sb.append(aChar);
            }
        }
        return sb.toString();
    }

    /**
     * 1913. 两个数对之间的最大乘积差
     *
     * @param nums
     * @return
     */
    public int maxProductDifference(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length - 1] * nums[nums.length - 2] - nums[0] * nums[1];
    }

    /**
     * 1909. 删除一个元素使数组严格递增
     *
     * @param nums
     * @return
     */
    public boolean canBeIncreasing(int[] nums) {
        return true;
    }

    /**
     * 5800. 基于排列构建数组
     *
     * @param nums
     * @return
     */
    public int[] buildArray(int[] nums) {
        int[] ans = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            ans[i] = nums[nums[i]];
        }
        return ans;
    }

    /**
     * 5800. 基于排列构建数组
     *
     * @param nums
     * @return
     */
    public int[] buildArray2(int[] nums) {
        // 第一次遍历编码最终值
        for (int i = 0; i < nums.length; ++i) {
            nums[i] += 1000 * (nums[nums[i]] % 1000);
        }
        System.out.println(Arrays.toString(nums));
        // 第二次遍历修改为最终值
        for (int i = 0; i < nums.length; ++i) {
            nums[i] /= 1000;
        }
        return nums;
    }

    /**
     * 1921. 消灭怪物的最大数量
     *
     * @param dist
     * @param speed
     * @return
     */
    public int eliminateMaximum(int[] dist, int[] speed) {
        int[] time = new int[dist.length];
        for (int i = 0; i < dist.length; i++) {
            time[i] = ((dist[i] - 1) / speed[i]);
        }
        Arrays.sort(time);
        for (int i = 0; i < time.length; i++) {
            if (time[i] < i) {
                return i;
            }
        }
        return time.length;
    }

    /**
     * 1903. 字符串中的最大奇数
     *
     * @param num
     * @return
     */
    public String largestOddNumber(String num) {
        char[] chars = num.toCharArray();
        int index = 0;
        for (int i = chars.length - 1; i >= 0; i--) {
            if ((chars[i] & 1) == 1) {
                index = i;
                break;
            }
        }
        return new String(chars, 0, index);
    }

//    public static void main(String[] args) {
//        IsCousinsSolution2 isCousinsSolution2 = new IsCousinsSolution2();
//        isCousinsSolution2.numberOfRounds("12:01", "12:44");
//    }

    /**
     * 1904. 你完成的完整对局数
     *
     * @param startTime
     * @param finishTime
     * @return
     */
    public int numberOfRounds(String startTime, String finishTime) {
        String[] startTimes = startTime.split(":");
        String[] finishTimes = finishTime.split(":");
        int startHour = Integer.parseInt(startTimes[0]);
        int finishHour = Integer.parseInt(finishTimes[0]);
        int startMinute = Integer.parseInt(startTimes[1]);
        int finishMinute = Integer.parseInt(finishTimes[1]);
        int count = 0;
        if (startHour < finishHour) {
            count += ((finishHour - startHour - 1) << 2);
        } else if (startHour == finishHour) {
            if (startMinute < finishMinute) {
                count -= 4;
            } else {
                count += (23 << 2);
            }
        } else {
            count += ((23 + finishHour - startHour) << 2);
        }
        count += getStartMinuteCount(startMinute);
        count += getFinishMinuteCount(finishMinute);
        return count;
    }

    private int getFinishMinuteCount(Integer finishMinute) {
        if (finishMinute < 15) {
            return 0;
        } else if (finishMinute < 30) {
            return 1;
        } else if (finishMinute < 45) {
            return 2;
        }
        return 3;
    }

    private int getStartMinuteCount(Integer startMinute) {
        if (startMinute == 0) {
            return 4;
        } else if (startMinute <= 15) {
            return 3;
        } else if (startMinute <= 30) {
            return 2;
        } else if (startMinute <= 45) {
            return 1;
        }
        return 0;
    }

    public static void main(String[] args) {
        canBeTypedWords("hello world", "ad");

        Set<String> set = new HashSet<>();
        System.out.println(set.stream().findFirst().orElseGet(() -> "1"));
        set.add("11111");
        System.out.println(set.stream().findFirst().get());
    }

    public static int canBeTypedWords(String text, String brokenLetters) {
        String[] strings = text.split(" ");
        if (brokenLetters == null || brokenLetters.length() == 0) {
            return strings.length;
        }
        char[] chars = brokenLetters.toCharArray();
        Set<Character> set = new HashSet<>();
        for (char aChar : chars) {
            set.add(aChar);
        }
        int count = 0;
        for (String string : strings) {
            for (char c : string.toCharArray()) {
                if (set.contains(c)) {
                    count++;
                    break;
                }
            }
        }
        return strings.length - count;
    }


    public static int canBeTypedWords2(String text, String brokenLetters) {
        char[] chars = brokenLetters.toCharArray();
        Set<Character> set = new HashSet<>();
        for (char aChar : chars) {
            set.add(aChar);
        }
        int res = 0;
        boolean flag = true;
        for (char c : text.toCharArray()) {
            if (c == ' ') {
                if (flag) {
                    res++;
                }
                flag = true;
            } else if (set.contains(c)) {
                flag = false;
            }
        }
        if (flag) {
            res++;
        }
        return res;
    }


    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        Set<ListNode> set = new HashSet<>();
        ListNode tempNode = headA;
        while (tempNode != null) {
            set.add(tempNode);
            tempNode = tempNode.next;
        }
        tempNode = headB;
        while (tempNode != null) {
            if (set.contains(tempNode)) {
                return tempNode;
            }
            tempNode = tempNode.next;
        }
        return null;
    }

    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
       if (headA == null || headB == null) {
           return null;
       }
       ListNode pA = headA, pB = headB;
       while (pA != pB) {
           pA = pA == null ? pA : pA.next;
           pB = pB == null ? pB : pB.next;
       }
       return pA;
    }

    /**
     * 1893. 检查是否区域内所有整数都被覆盖
     *
     * @param ranges
     * @param left
     * @param right
     * @return
     */
    public boolean isCovered(int[][] ranges, int left, int right) {
        boolean[] flag = new boolean[51];
        for (int[] range : ranges) {
            for (int i = range[0]; i <= range[1]; i++) {
                flag[i] = true;
            }
        }
        for (int i = left; i <= right; i++) {
            if (!flag[i]) {
                return false;
            }
        }
        return true;
    }

    /**
     * 1893. 检查是否区域内所有整数都被覆盖
     *
     * @param ranges
     * @param left
     * @param right
     * @return
     */
    public boolean isCovered2(int[][] ranges, int left, int right) {
        Arrays.sort(ranges, (a1, a2) -> a1[0] - a2[0]);
        for (int[] range : ranges) {
            int l = range[0];
            int r = range[1];
            if (left >= l && left <= r) {
                left = r + 1;
            }
        }
        return left > right;
    }


    /**
     * 1893. 检查是否区域内所有整数都被覆盖
     *
     * @param ranges
     * @param left
     * @param right
     * @return
     */
    public boolean isCovered3(int[][] ranges, int left, int right) {
        boolean[] flag = new boolean[51];
        for (int[] range : ranges) {
            int L = Math.max(range[0], left);
            int R = Math.min(range[1], right);
            for (int i = L; i <= R; i++) {
                flag[i] = true;
            }
        }
        for (int i = left; i <= right; i++) {
            if (!flag[i]) {
                return false;
            }
        }
        return true;
    }
}

class ListNode {
      int val;
      ListNode next;
     ListNode(int x) {
          val = x;
          next = null;
      }
 }

@Data
@AllArgsConstructor
@NoArgsConstructor
class DailyRealPublishInfo {
    private String orderId;

    private LocalDate date;

    private BigDecimal consumeAmount = BigDecimal.ZERO;

    private BigDecimal compensateCostAmount = BigDecimal.ZERO;
}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

/**
 * 225. 用队列实现栈
 */
class MyStack {

    private Queue<Integer> firstQuque;
    private Queue<Integer> secondQuque;

    /**
     * Initialize your data structure here.
     */
    public MyStack() {
        firstQuque = new LinkedList<>();
        secondQuque = new LinkedList<>();
    }

    /**
     * Push element x onto stack.
     */
    public void push(int x) {
        if (!firstQuque.isEmpty()) {
            firstQuque.offer(x);
        }
        secondQuque.offer(x);

    }

    /**
     * Removes the element on top of the stack and returns that element.
     */
    public int pop() {
        if (empty()) return -1;
        int x = -1;
        if (!firstQuque.isEmpty()) {
            int size = firstQuque.size();
            while (!firstQuque.isEmpty()) {
                x = firstQuque.poll();
                if (size-- > 1) {
                    secondQuque.offer(x);
                }
            }
        } else {
            int size = secondQuque.size();
            while (!secondQuque.isEmpty()) {
                x = secondQuque.poll();
                if (size-- > 1) {
                    firstQuque.offer(x);
                }
            }
        }
        return x;
    }

    /**
     * Get the top element.
     */
    public int top() {
        if (empty()) return -1;
        int x = -1;
        if (!firstQuque.isEmpty()) {
            while (!firstQuque.isEmpty()) {
                x = firstQuque.poll();
                secondQuque.offer(x);
            }
        } else {
            while (!secondQuque.isEmpty()) {
                x = secondQuque.poll();
                firstQuque.offer(x);
            }
        }
        return x;
    }

    /**
     * Returns whether the stack is empty.
     */
    public boolean empty() {
        return firstQuque.isEmpty() && secondQuque.isEmpty();
    }
}

/**
 * 225. 用队列实现栈
 */
class MyStack2 {

    private Queue<Integer> firstQuque;
    private Queue<Integer> secondQuque;

    /**
     * Initialize your data structure here.
     */
    public MyStack2() {
        firstQuque = new LinkedList<>();
        secondQuque = new LinkedList<>();
    }

    /**
     * Push element x onto stack.
     */
    public void push(int x) {
        secondQuque.offer(x);
        while (!firstQuque.isEmpty()) {
            secondQuque.offer(firstQuque.poll());
        }
        Queue<Integer> queue = firstQuque;
        firstQuque = secondQuque;
        secondQuque = queue;

    }

    /**
     * Removes the element on top of the stack and returns that element.
     */
    public int pop() {
        return firstQuque.poll();
    }

    /**
     * Get the top element.
     */
    public int top() {
        return firstQuque.peek();
    }

    /**
     * Returns whether the stack is empty.
     */
    public boolean empty() {
        return firstQuque.isEmpty();
    }
}

/**
 * 225. 用队列实现栈
 */
class MyStack3 {

    private Queue<Integer> quque;

    /**
     * Initialize your data structure here.
     */
    public MyStack3() {
        quque = new LinkedList<>();
    }

    /**
     * Push element x onto stack.
     */
    public void push(int x) {
        int n = quque.size();
        quque.offer(x);
        for (int i = 0; i < n; i++) {
            quque.offer(quque.poll());
        }

    }

    /**
     * Removes the element on top of the stack and returns that element.
     */
    public int pop() {
        return quque.poll();
    }

    /**
     * Get the top element.
     */
    public int top() {
        return quque.peek();
    }

    /**
     * Returns whether the stack is empty.
     */
    public boolean empty() {
        return quque.isEmpty();
    }
}